import java.util.Arrays;

/**
 * @program: data_structures_algorithms
 * @description: 基数排序，是稳定的排序算法
 * @author: lld
 * @create: 2020-10-12 19:31
 **/

public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {53, 3, 542, 748, 14, 214};
        radixSort(arr);
    }

    public static void radixSort(int[] arr) {
        //定义二维数组表示10个桶，代表0-9个位数
        //不能具体最大桶的长度，防止溢出，每个桶长度为arr.length
        //基数排序是空间换时间
        int[][] bucket = new int[10][arr.length];

        //为了记录每个桶放入数据个数,bucketCount[0]代表bucket[0]的个数
        int[] bucketCount = new int[10];
        //获取数组中最大的位数
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        //数转字符串,位数即字符串长度
        int maxLength = String.valueOf(max).length();
        //根据位数循环
        for (int c = 0; c < maxLength; c++) {

            for (int i = 0; i < arr.length; i++) {
                int digit = (int) (arr[i] / Math.pow(10, c) % 10);
                bucket[digit][bucketCount[digit]] = arr[i];
                bucketCount[digit]++;
            }
            //将排序一次桶里的数放入原来的数组
            int index = 0;
            for (int i = 0; i < bucketCount.length; i++) {
                //判断桶是否有数据
                if (bucketCount[i] != 0) {
                    //循环第i个一维数组
                    for (int j = 0; j < bucketCount[i]; j++) {
                        arr[index] = bucket[i][j];
                        index++;
                    }
                }
//                第i轮处理后清空bucketCount[i]
                bucketCount[i] = 0;
            }
            System.out.println(c + 1 + "次排序：" + Arrays.toString(arr));
        }
    }
}
